The present invention relates to the field of computer graphics animation, and more specifically to techniques for specifying animation using splines whose values are calculated using a set of linear equations.
In traditional computer graphics animation, the motion of an object or character in a scene is generally specified by a set of splines or animation curves which describe the way its parameters change over time. The X axis of a spline generally corresponds to time and the Y axis corresponds to the parameter's value as it changes over time. An animator may specify constraints in the form one or more knots and the spline interpolates or approximates the knots.
Use of splines provides excellent control of the motion since the splines simply approximate or interpolate a series of key values or knots carefully crafted by an animator. Traditional splines have thus become very powerful tools in the hands of animators. Unfortunately, traditional spline techniques provide little help to an animator in producing physically realistic motion. This is because the behavior of the splines is only very tenuously related to the underlying physics of motion. For example, splines exhibit perfect time symmetry, while real motion is decidedly asymmetric in time. Accordingly, any physical realism in the motion using traditional splines comes not from the mathematics of the splines themselves, but from the talent, skill, insight and sweat of the animator [Lasseter 1987] (a list of references is provided below before the claims section).
When greater physical realism is desired, or when the required animator time would be too expensive, direct physical simulation of the underlying physics is sometimes used to create computer graphics motion. While physical simulation can create compelling realism of motion, it is often very difficult to control, and simulations can produce surprising or unintended results. Determining the proper applied forces and physical parameters necessary to achieve a particular desired effect is generally a formidable challenge. The central problem in ordinary simulation is that simulation equations march forward in time from initial conditions to a final result. Forces lead to accelerations which are integrated to get velocities and positions over time. If the result at some point in time is not what is desired, it is usually very difficult to determine how the forces and parameters before hand have to be changed to bring the motion closer to the goal.
In 1988, Witkin and Kass [Witkin 1988] developed a technique called Spacetime Constraints to try to marry the physical realism of simulation with the controllability and predictability of traditional splines. Their idea was to have animators continue to specify key values of parameters over time, but interpolate the motion in the most physically realistic way possible subject to these constraints. For example, instead of demanding that Newton's second law, f=ma be satisfied all the time as in a traditional simulation, the Spacetime Constraints formalism minimizes the deviation from the second law while guaranteeing the interpolation constraints set by the animators are met.
Although the Spacetime Constraints approach has the potential to provide the elusive combination of realism, predictability and control sought after in computer graphics production, it has thus far remained the realm of academic research for at least two reasons. Foremost among the difficulties in using Spacetime Constraints is the complexity involved. The full equations of motion for even simple object models are tremendously complicated and required an elaborate symbolic math-based compiler to evaluate. Even if the equations of motion of interesting character models can be managed, a second obstacle is the execution time of the required nonlinear optimization. Animators are loath to use any technique which slows an animation system down from interactive speeds. Full character-level Spacetime Constraint problems cannot presently be solved fast enough with existing formulations.
A variety of researchers have applied the Spacetime Constraints approach to specific domains, used different optimization methods, tried accelerate it, or addressed other weaknesses in the original formulation (e.g., [Cohen 1992], [Ngo 1993], [Liu 1994], [Witkin 1995], [Rose 1996], [Gleicher 1997], [Popovic 1999], [Popovic 2000], [Fang 2003], [Treuille 2003], [Safonova 2004]). Good summaries of the specific contributions and evolution of the ideas can be found in [Fang 2003] and [Safonova 2004]. However, these techniques do not provide the interactivity and control desired by animators.